/*
 * @lc app=leetcode.cn id=343 lang=cpp
 *
 * [343] 整数拆分
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int integerBreak(int n)
    {
        vector<int> dp(n + 1, 0);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;

        for (int i = 3; i <= n; i++)
        {
            for (int j = 1; j <= i / 2; j++)
            {
                dp[i] = std::max(dp[i],
                                 std::max(dp[j], j) * std::max(dp[i - j], i - j));
            }
        }
        return dp[n];
    }
};

// int main(int argc, char const *argv[])
// {
//     Solution s;
//     for(int i = 3; i < 50; i++)
//     {
//         cout << s.integerBreak(i) << endl;
//     }
//     return 0;
// }


// @lc code=end
